package com.ztom.top100;

/**
 * 正则表达式匹配
 * <p>
 * https://leetcode-cn.com/problems/regular-expression-matching/
 *
 * @author ZhangTao
 */
public class Code06IsMatch {

    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        char[] str = s.toCharArray();
        char[] pStr = p.toCharArray();
        return process(str, pStr, str.length, pStr.length);
    }

    /**
     * 从两字符串末尾开始匹配, 将已匹配的部分移除掉
     *
     * @param s  目标字符串
     * @param p  模式字符串
     * @param sl 目标字符串长度
     * @param pl 模式字符串长度
     * @return 是否匹配
     */
    private boolean process(char[] s, char[] p, int sl, int pl) {
        if (sl == 0 && pl == 0) {
            // 两个字符串长度都是 0
            return true;
        }
        if (pl == 0) {
            // s 字符串不为空, p 字符串是空, 一定无法匹配
            return false;
        }
        if (sl == 0) {
            // s 字符串为空, 那么 p: a*b*c* 是可以匹配的
            // p 最后一位必须是 *, 去掉最后两个字符(相当于末尾的 * 匹配 0 次)
            return p[pl - 1] == '*' && process(s, p, sl, pl - 2);
        }
        // s 和 p 都不为空
        if (p[pl - 1] == '*' && pl - 2 >= 0) {
            // p 末尾字符是 *
            if (s[sl - 1] == p[pl - 2] || p[pl - 2] == '.') {
                // 如果前一个字符可以匹配, * 可以匹配 0 次、 1 次或多次
                return process(s, p, sl, pl - 2) || process(s, p, sl - 1, pl);
            } else {
                // 如果前一个字符不匹配, 那么 * 匹配 0 次
                return process(s, p, sl, pl - 2);
            }
        } else {
            // p 末尾字符不是 *
            return (s[sl - 1] == p[pl - 1] || p[pl - 1] == '.') && process(s, p, sl - 1, pl - 1);
        }
    }

    public boolean isMatch2(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        char[] str = s.toCharArray();
        char[] pStr = p.toCharArray();
        int m = str.length;
        int n = pStr.length;

        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int pl = 1; pl <= n; pl++) {
            if (pStr[pl - 1] == '*' && pl - 2 >= 0) {
                dp[0][pl] = dp[0][pl - 2];
            }
        }
        for (int sl = 1; sl <= m; sl++) {
            for (int pl = 1; pl <= n; pl++) {
                if (pStr[pl - 1] == '*' && pl - 2 >= 0) {
                    if (str[sl - 1] == pStr[pl - 2] || pStr[pl - 2] == '.') {
                        dp[sl][pl] = dp[sl][pl - 2] || dp[sl - 1][pl];
                    } else {
                        dp[sl][pl] = dp[sl][pl - 2];
                    }
                } else {
                    if (str[sl - 1] == pStr[pl - 1] || pStr[pl - 1] == '.') {
                        dp[sl][pl] = dp[sl - 1][pl - 1];
                    }
                }
            }
        }
        return dp[m][n];
    }
}
